A navigation system performs travel guidance for enabling a user to easily and quickly reach a selected destination. A typical example is a vehicle navigation system where a vehicle is equipped with a navigation function. Such a navigation system detects the position of the user or user's vehicle, and reads out map data pertaining to an area at the current vehicle position from a map storage medium. The navigation system displays a map image on a monitor screen while superimposing a mark representing the current location of the user on the map image. When a destination is set, the navigation system starts a route guidance function for setting a guided route from the start point to the destination based on the map data. The navigation system calculates and determines an optimum route, such as a shortest route to the destination based on various parameters.
To determine a route to a destination, currently available vehicle navigation systems typically employ a search algorithm called an “A*” algorithm which is based on the graphic search technique used in the artificial intelligence (AI). In general, the A* algorithm performs a directed search through the graph, i.e., map data, from the start point to the destination, by building a tree of possible solution paths as it progresses, the root of the tree being the source segment.
The A* algorithms iterates by determining all of the nearest connected segments to each “branch” or tree segment beginning with the start point (current vehicle position VP) segment. A cost (f(n)) for each segment is then determined according to the formula:f(n)=g(n)+h(n)  (1)where g(n) represents the known cost from the source segment to segment n, and h(n) representing the heuristic cost from a segment n to the destination. The heuristic cost is essentially an intelligent guess of the actual cost (distance, time, money, etc) from the segment n to the destination. The segment with the lowest overall cost is then selected as a part of the route and the algorithm continues until a segment corresponding to the desired destination is selected. The use of the cost formula in equation (1) has the effect of progressively narrowing the search area toward the destination.
The search may be conducted from the start point to the destination. In the alternative, the search may be conducted from both the start point to the destination and from the destination to the start point simultaneously. An example of this two ended search is shown in FIGS. 1A and 1B. In this example, the navigation system simultaneously searches a route from the current vehicle position (start point) VP to the destination Dst. Two elliptic marks A1 and A2 indicate general search directions and search areas for the search operations using the A* algorithm.
Basically, the search direction is on a direct line connecting the vehicle position VP and the destination Dst. The elliptic marks A1 and A2 are established from the vehicle position VP to the destination Dst and vice versa to limit the search directions and search areas. As the search progresses, the segments of routes from the vehicle position VP and to the destination Dst meet to create a completed route (calculated route) that connects the current vehicle position VP and the destination Dst.
Through the A* algorithm search, the navigation system can generally find an optimum route to a destination based on various cost parameters. For example, the optimum route is determined based on the shortest way to reach the destination, the quickest way to reach the destination, the route preferring freeways to surface roads, the least expensive route to the destination, the route without using toll road, or the like. However, in some cases, a conventional method utilizing the A* algorithm search fails to find an appropriate route to the destination. Such an example is explained below with reference to FIGS. 2A and 2B and FIG. 3.
FIGS. 2A and 2B are schematic diagrams showing the situation where the two ended search using the A* algorithm is used for a route calculation from a vehicle position VP to a destination Dst when a large area of non-digitized map data exists between them. In the situation shown in FIGS. 2A and 2B, there is a large lake 11 between the vehicle position VP and the destination Dst. The lake 11 is regarded as a non-digitized area because there are no road segments in the map data in the navigation system with respect to the inner area of the lake 11. Similar situation may arise for deserts, high mountains, jungles, swamp, etc.
When the navigation system starts to search a route, the navigation system will attempt to search in the directions and areas shown in search areas SA1 and SA2 indicated by hyperbolic curves. As noted above, ordinarily, the A* algorithm search attempts to search routes in the predetermined areas in the direction between the vehicle position and the destination defined by the search areas SA1 and SA2. The A* algorithm usually reduces heuristic cost by selecting a road segment that heads closer to a destination point. However, as shown in FIG. 2B, because there is no roads or paths within the lake 11, the route search in the direction and ranges indicated by search areas SA1 and SA2 toward the lake 11 becomes meaningless.
Therefore, in such a situation, a route search must be conducted without limiting the direction and area of search to find a route to the destination. Referring to FIG. 3, a possible fault is illustrated that may result from such a route search when a large non-digitized area exists between the current vehicle position VP and the destination Dst. As a result of such a route search operation between the vehicle position VP and the destination Dst without limiting the search directions and areas, the navigation system may produce a calculated route to the destination Dst using routes R1 and R3 as shown in FIG. 3.
However, although this route can guide the user to the destination Dst, it is not a very efficient route because the search directions and areas are not limited during the search. As indicated in FIG. 3, the user can reach the destination with a shorter distance by taking a route R2 instead of taking the route R1 in the first place. Namely, in the conventional technology, due to the lake 11 which does not have any road segments, the route search procedure is forced to proceed without limiting the search direction to avoid the lake 11. As a result, the navigation system tends to fail in detecting an optimum route such as a one using the route R2 in the example of FIG. 3.
Therefore, it is desired that a navigation system overcomes the shortcomings described above so that it can find an efficient route to a destination even when a large non-digitized area exists between the starting point and the destination.